home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_10_08 / 1008060a < prev    next >
Text File  |  1992-05-27  |  14KB  |  523 lines
  1. /*
  2. Postman's Sort (R) Version 1.0
  3. Copyright (c) Robert Ramey 1991. All Rights Reserved
  4. */
  5.  
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <time.h>
  9. #include <assert.h>
  10. #include <links.h>
  11. #include "psort.h"
  12. #include "sublist.h"
  13. #include "key.h"
  14. #include "io.h"
  15. #include "os.h"
  16.  
  17. #define FILE_GUESS 50000
  18. #define RECORD_SIZE_GUESS 80
  19. #define NSIZE 31
  20.     /* default maximum number of digits left of radix point */
  21.     /* don't increase this beyond 127 */
  22. #define MAX_BYTES_PER_PASS 8
  23.  
  24. /*********************************************************************
  25. The following structure contains one member for each byte on which a
  26. record may be distributed.  That is, if a sublist is to be distribiuted
  27. on the first two letters of an alphabetic key, the first tow members of
  28. the table will be used.  In this example byte_count will equal 2.
  29. **********************************************************************/
  30. typedef struct {
  31.     unsigned int *value;    /* points to sequence value array */
  32.     unsigned int order;    /* number of possible sequence values for this byte */
  33.     unsigned int count;    /* number of sublists to skip to get to next one */
  34.     unsigned int key_index;    /* index of key where this byte is found */
  35.     unsigned int field_index; /* key_index + 1 */
  36.     unsigned int depth;        /* displacement within key where byte is found */
  37. } BYTE_TABLE;
  38.  
  39. /*********************************************************************
  40. The following data stores the state of sublist arrays and sort keys
  41. **********************************************************************/
  42. typedef struct {
  43.     SUBLIST *sublist;
  44.     unsigned int
  45.         sublist_count,    /* number of sublists at this level */
  46.         byte_count;        /* number of bytes to test on current pass */
  47.     struct {
  48.         unsigned int
  49.             icount, /* number of frames in environment */
  50.             count;    /* number of data frames so far in memory */
  51.         FILE_SIZE
  52.             limit,    /* amount of memory to be cleared to disk at */
  53.                         /* at a time */
  54.             size;    /* amount filled in current frame */
  55.     } frame;
  56.     BYTE_TABLE byte_table[MAX_BYTES_PER_PASS];
  57.                         /* see above for explanation of BYTE TABLE */
  58. } ENVIRONMENT;
  59.  
  60. /*********************************************************************
  61. global data
  62. **********************************************************************/
  63. BOOLEAN uflag = FALSE;        /* unique flag value */
  64. RECORD *(*infunc)();    /* pointer to function which gets next record */
  65. MEM_SIZE seg_length = 16;    /* default size of stack segment */
  66. unsigned int max_sublists = 0;
  67.                         /* maximum number of sublists / segment */
  68. ENVIRONMENT *env_ptr = (ENVIRONMENT *)NULL;
  69.                         /* pointer to current environment */
  70. void
  71. sort();
  72. private void
  73. psort(unsigned int, unsigned int, SUBLIST *);
  74. private unsigned int
  75. plan(ENVIRONMENT *, unsigned int, unsigned int, unsigned long, FILE_SIZE);
  76. private int
  77. dist(SUBLIST *, SUBLIST*);
  78. private void
  79. dsort(SUBLIST *, unsigned int);
  80. private void
  81. nsort(SUBLIST *, unsigned int);
  82. private RECORD *
  83. list_input(SUBLIST *);
  84. private void
  85. fill_fields(RECORD *);
  86. private BOOLEAN
  87. fits(FILE_SIZE, unsigned int);
  88. void *
  89. need(STACK *, size_t);
  90. void *
  91. get_space(STACK *, size_t);
  92. private void
  93. display_out(clock_t);
  94. private clock_t
  95. display_in(unsigned int, unsigned int, long, ENVIRONMENT *);
  96. private void
  97. free_memory(FILE_SIZE);
  98. private void
  99. free_frames(unsigned int);
  100. /*********************************************************************
  101. sort - top level driver for sort engine
  102. **********************************************************************/
  103. void
  104. sort(){
  105.     ENVIRONMENT env;    /* dummy initial environment */
  106.     unsigned int n;
  107.     unsigned long rc;
  108.     FILE_SIZE fsize;
  109.     clock_t time;
  110.  
  111.     /* miniature version of sort */
  112.     /* for a full explanation see below */
  113.  
  114.     /* try to guess file size */
  115.     fsize = os_flength(stdin);
  116.     if(fsize <= 0L)
  117.         fsize = FILE_GUESS;
  118.  
  119.     rc = fsize / (record_size ? record_size : RECORD_SIZE_GUESS);
  120.     n = plan(&env, 0, 0, rc, fsize);
  121.     env.sublist = sublist_allocate(n);
  122.     env.sublist_count = n;
  123.  
  124.     /* initialize stacks */
  125.     assert(stk_push(d_stack));
  126.  
  127.     env.frame.limit = (FILE_SIZE) rb_size * n * K;
  128.     env.frame.size = 0;
  129.     env.frame.icount =
  130.     env.frame.count = 1;
  131.     env_ptr = &env;
  132.  
  133.     sublist_fclose();
  134.  
  135.     time = display_in(0, 0, 0L, &env);
  136.  
  137.     dist((SUBLIST *)NULL, env.sublist);
  138.  
  139.     display_out(time);
  140.  
  141.     infunc = sublist_input;
  142.  
  143.     dsort(env.sublist, 0);
  144.  
  145.     stk_pop(d_stack);
  146.     stk_free(d_stack);
  147.  
  148.     return;
  149. }
  150. /*************************************************************
  151. psort - distribution sort
  152. **************************************************************/
  153. private
  154. void
  155. psort(key_index, depth, sublist)
  156. unsigned int
  157.     key_index,
  158.     depth;
  159. SUBLIST *sublist;
  160. {
  161.     ENVIRONMENT
  162.         *prev_env,    /* pointer to previous environment */
  163.         env;        /* current set fo environment variables */
  164.     clock_t time;    /* used to record time function started */
  165.  
  166.     /* use statics to save stack space for 2nd order recurrsive function */
  167.     static unsigned int n;
  168.                     /* number of sublists needed by on this pass */
  169.     static long record_count;
  170.                     /* number of records in the input sublist */
  171.  
  172.     record_count  = sublist->pcount + sublist->count;
  173.  
  174.     /* take care of end points */
  175.     if(record_count == 0)
  176.         return;
  177.     if(record_count == 1){
  178.         sublist_output(sublist, uflag);
  179.         return;
  180.     }
  181.  
  182.     /* there are no more keys we're done */
  183.     if(key_index >= key_count){
  184.         sublist_output(sublist, uflag);
  185.         return;
  186.     }
  187.  
  188.     /* if current key is exhausted */
  189.     if(depth >= key[key_index].size){
  190.         /* move on to the next one */
  191.         depth = 0;
  192.         /* if that was the last key we're done */
  193.         if(++key_index >= key_count){
  194.             sublist_output(sublist, uflag);
  195.             return;
  196.         }
  197.     }
  198.  
  199.     /* figure out how many key bytes to use in distribution */
  200.     /* and fill them into byte table of new environment */
  201.     n = plan(&env, key_index, depth, record_count, sublist->size);
  202.  
  203.     /* allocate the calculated number of sublists, creating a new */
  204.     /* memory area if necessary */
  205.     env.sublist = sublist_allocate(n);
  206.     env.sublist_count = n;
  207.  
  208.     /* save state of storage */
  209.     /* try to be sure that memory exists for next pass */
  210.     free_memory(sublist->size);
  211.  
  212.     assert(stk_push(d_stack));
  213.     env.frame.limit = (FILE_SIZE) rb_size * n * K;
  214.     env.frame.size = 0;
  215.     env.frame.icount =
  216.     env.frame.count = env_ptr->frame.count+1;
  217.  
  218.     /* close switch to other swap file */
  219.     sublist_fclose();
  220.  
  221.     /* save pointer to previous environment for end of function */
  222.     prev_env = env_ptr;
  223.     env_ptr = &env;
  224.  
  225.     time = display_in(key_index, depth, record_count, &env);
  226.  
  227.     /* distribute the input sublist among the new sublists */
  228.     /* according to the key bytes specified in the byte table*/
  229.     n = dist(sublist, env.sublist);
  230.  
  231.     if(n = 0){
  232.         /* reuse space used by sublist array */
  233.         *sublist = (env.sublist)[n];
  234.         env.sublist = sublist;
  235.         env.sublist_count = 1;
  236.         sublist_shrink();
  237.         dsort(env.sublist, env.byte_count);
  238.     }
  239.     else{
  240.         /* sort sublists in the proper sequence */
  241.         dsort(env.sublist, 0);
  242.     }
  243.  
  244.     /* and recover environment of caller */
  245.     sublist_free();
  246.     do{
  247.         assert(stk_pop(d_stack));
  248.     }while(env.frame.count-- > env.frame.icount);
  249.     env_ptr = prev_env;
  250.     display_out(time);
  251.     return;
  252. }
  253. /*********************************************************************
  254. plan - Figure how many sublists should be created for distributing the
  255. current sublist.  Figure how many bytes should be used to determine
  256. where a record will be distributed.
  257. **********************************************************************/
  258. private
  259. unsigned int
  260. plan(env_ptr, key_index, depth, record_count, fsize)
  261. ENVIRONMENT *env_ptr;/* address of environment where new byte table is*/
  262.                     /* to be loaded */
  263. unsigned int
  264.     key_index,        /* where the next key starts */
  265.     depth;
  266. unsigned long record_count;
  267.                     /* number of records in sublists to be distributed */
  268. FILE_SIZE fsize;    /* total size of sublist records in bytes */
  269. {
  270.     unsigned int i, j, sublist_count;
  271.     BYTE_TABLE *bptr;
  272.  
  273.     /* initialize accumulators */
  274.     env_ptr->byte_count = 0;
  275.     bptr = env_ptr->byte_table;
  276.     sublist_count = 1;
  277.  
  278.     /* figure how many bytes we can handle at a time */
  279.     for(;;){
  280.  
  281.